package cxydmmszl.chapter05.t089.middle2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 *
 * <li style="color: green;">Desc</li>
 * 给定一个字符串 str，再给定 str 的最长回文子序列字符串 strlps,
 * 请返回在添加字符最少的情况下，让 str 整体都是回文字符串的一种结果。
 * 进阶问题比原问题多了一个参数，请做到时间复杂度比原问题的实现低。
 * <li style="color: green;">Input</li>
 * 输出包含两行，第一行包含一个字符串代表 str（1≤length(str)≤5000），
 * 第二行包含一个字符串，代表 strlps。
 * <li style="color: green;">Output</li>
 * 输出一行，代表返回的值。
 * <li style="color: blue;">Link</li> CD125
 *
 * @author habitplus
 * @since 2021-09-12 13:50
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String strlps = br.readLine();
        br.close();

        str = solve(str, strlps);
        System.out.println(str);
    }

    private static String solve(String str, String strlps) {

        if (str == null || str.length() == 0) {
            return "";
        }

        char[] strChs = str.toCharArray();
        char[] lpsChs = strlps.toCharArray();
        int strLen = strChs.length;
        int lpsLen = lpsChs.length;

        char[] res = new char[2 * strLen - lpsLen];

        int strL = 0, lpsL = 0, l = 0;
        int strR = strLen - 1, lpsR = lpsLen - 1, r = res.length - 1;
//        int tmpL, tmpR;
        while (lpsL <= lpsR) {
//            tmpL = strL;
//            tmpR = strR;
            while (strChs[strL] != lpsChs[lpsL]) {
                res[l++] = strChs[strL];
                res[r--] = strChs[strL];
                strL++;
            }
            while (strChs[strR] != lpsChs[lpsR]) {
                res[l++] = strChs[strR];
                res[r--] = strChs[strR];
                strR--;
            }

            res[l++] = strChs[strL++];
            res[r--] = strChs[strR--];
            lpsL++;
            lpsR--;
        }

        return String.valueOf(res);
    }
}
